package com.su.test;

import org.bouncycastle.util.Arrays;

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.TreeSet;

public class Aalgorithm extends Strategy{


    public Aalgorithm() {
    }


    public void run(){

        super.steps = 0;
        //open表
        Queue<Node> openQueue = new PriorityQueue<Node>((o1,o2)->{
            if(o1.evaluation > o2.evaluation)
                return 1;
            else if(o1.evaluation < o2.evaluation)
                return -1;
            return 0;
        });

        int emptyIndex=0;     //记录空格的位置
        int misposition=0;    //数码不在位的个数
        for (int i = 0; i < length; i++) {
            if(initArr[i] == 0){
                emptyIndex = i;
            }
            if(initArr[i] != targetArr[i])
                misposition++;

        }
        Node initNode = new Node(initArr,misposition,emptyIndex,null);
        openQueue.add(initNode);
        //close表
        Set<Node> closeSet = new TreeSet<Node>();

        while (!openQueue.isEmpty()){
            super.steps++;      //记录步数

            Node curNode = openQueue.poll();

            //当前节点是目标节点
            if(curNode.misposition == 0){
                super.lastNode = curNode;
                return;
            }

            int mispositionOfCur = curNode.misposition;//当前节点“不在位”的个数
            int emptyIndexOfCur = curNode.emptyIndex;   //当前节点空格位置

            //左移
            if(emptyIndexOfCur % this.col > 0){
                int nextArr[] = move(curNode.num,emptyIndexOfCur,-1);
                int differNum = differ(curNode.num,emptyIndexOfCur,-1);
                Node nextNode = new Node(nextArr,differNum + mispositionOfCur,emptyIndexOfCur -1,curNode);
                if(!closeSet.contains(nextNode)){
                    openQueue.add(nextNode);
                }
            }
            //上移
            if(emptyIndexOfCur > this.col){
                int nextArr[] = move(curNode.num,emptyIndexOfCur,-this.col);
                int differNum = differ(curNode.num,emptyIndexOfCur,-this.col);

                Node nextNode = new Node(nextArr,differNum + mispositionOfCur,emptyIndexOfCur - this.col,curNode);
                if(!closeSet.contains(nextNode)){
                    openQueue.add(nextNode);
                }
            }
            //右移
            if(emptyIndexOfCur % this.col < this.col - 1){
                int nextArr[] = move(curNode.num,emptyIndexOfCur,1);
                int differNum = differ(curNode.num,emptyIndexOfCur,1);
                Node nextNode = new Node(nextArr,differNum + mispositionOfCur,emptyIndexOfCur + 1,curNode);
                if(!closeSet.contains(nextNode)){
                    openQueue.add(nextNode);
                }
            }
            //下移
            if (emptyIndexOfCur < length - this.col){
                int nextArr[] = move(curNode.num,emptyIndexOfCur,this.col);
                int differNum = differ(curNode.num,emptyIndexOfCur,this.col);
                Node nextNode = new Node(nextArr,differNum + mispositionOfCur,emptyIndexOfCur +this.col,curNode);
                if(!closeSet.contains(nextNode)){
                    openQueue.add(nextNode);
                }
            }

            closeSet.add(curNode);

        }
    }



    /**
     * @Description         计算当前数码交换前和交换后的“不在位”的数码个数之差
     * @param curArr        当前数码
     * @param emptyIndex    当前数码空格位置
     * @param pos           空格偏移量
     **/
    private int differ(int curArr[],int emptyIndex,int pos){
        //判断移动前，空格位置和目标位置的元素和目标状态的八数码对应元素是否相同
        boolean beforeEmpty = curArr[emptyIndex] == targetArr[emptyIndex];
        boolean beforeTarget = curArr[emptyIndex + pos] == targetArr[emptyIndex + pos];

        //移位前，都是正确的，移位后肯定都错位
        if(beforeEmpty && beforeTarget)
            return 2;

            //移位前，有一个正确的，移位后肯定都错位
        else if(beforeEmpty || beforeTarget)
            return 1;

            //移位前都错位，再判断移位后的情况
        else{
            //判断移动后，空格位置和目标位置的元素和目标状态的八数码对应元素是否相同
            boolean afterEmpty = curArr[emptyIndex] == targetArr[emptyIndex + pos];
            boolean afterTarget = curArr[emptyIndex + pos] == targetArr[emptyIndex];
            if(afterEmpty && afterTarget)
                return -2;
            else if (afterEmpty || afterTarget)
                return -1;
            else
                return 0;
        }
    }
}
/*
    输入初始数组、目标数组
    创建两个表，OPEN表保存所有已生成而未考察的节点，
    CLOSED表中记录已访问过的节点。算起点的估价值，将起点放入OPEN表。
    while(open != NULL) {
        从open表中取出估价值f最小的节点n
        if(节点n == 目标节点){
            创建一个List,用来保存最佳路线的数组（表示八数码）
            while(节点n != NULL){
                将节点n的数组添加至List
                节点n = 节点n->parent
            }
            倒序输出List
        }
         for(当前节点n的每一个子节点X){
             计算子节点的估价值，
             if(子节点X not in Closed表)
                将子节点X加入Open表中
         }
         将当前节点n加入到Closed表中
    }

 */
